This invention relates to an apparatus and method for recognizing information addresses and, in particular, to an apparatus and method of this type for use with networks which carry information.
It is common practice in today's technology to connect multiple stations together to form a network. The advantage of a network is that the information and capabilities of each station on the network can be accessed and shared with the other stations on the network. A network which operates locally is typically referred to as a Local Area Network (LAN).
Individual LANs are generally limited in the number of stations that can be interconnected. In a typical LAN 20-100stations is the practical limit. However, with the significant acceptance and use of LANs, there has come an increased demand to build networks accommodating a larger number of stations (e.g., 4000-8000). This has been achieved by interconnecting individual LANs using so-called "bridges".
A bridge examines packets of information on a LAN and determines whether or not each packet needs to be forwarded to another attached LAN. The basic mechanism employed by a bridge to make these "filter/forward decisions" makes use of source and destination addresses carried by each information packet.
Using these addresses a bridge carries out a recognition procedure in which it compares the destination address of a received information packet with a database having the source addresses of all the stations located on the same LAN from which the bridge received the packet. If the destination address is contained in the source address database, the packet is destined for the same LAN and, as a result, the packet is filtered (not forwarded to the other attached LAN) by the bridge. If the destination address is not contained in the source address database, the packet is then forwarded by the bridge to the other LAN. The bridge also examines the source address of each information packet to see whether it has been previously stored in the database associated with the transmitting LAN. If it has not, the address is then stored so that the next time the same destination address appears, the bridge will find it in the database and filter the information.
To facilitate highspeed data throughput, a bridge must make a filter/forward decision and, thus, carry out the address recognition procedure in as short an amount of time as possible. One recognition technique employed in existing bridges which enables such rapid recognition makes use of a Content Addressable Memory (CAM). The high speed recognition of a CAM is accomplished by hardware that processes the comparison of each destination address with stored source addresses in parallel. Such implementation of the CAM, however, makes the CAM expensive and also severely limits its storage capability. As an illustration, CAMs that are commonly available are capable of storing 256 addresses corresponding to approximately 1200 bits of information. This compares with a Random Access Memory (RAM) that can today be obtained in the 1 Megabit range.
A second technique for implementing address recognition in existing bridges relies on the use of a RAM to store source addresses. The destination address of a received packet is then successively compared with each source address in the memory until a match is found or the memory exhausted. RAM storage offers the advantage that a very large number of source addresses can be economically stored. However, the time required to find a match is slow as compared to the CAM technique previously discussed.
To increase the speed of recognition when RAM storage is used, a hashing process may be added. Hashing requires a "hash" function that maps addresses into integers in the range 0 to k-1. Any hashing function of the source address that gives a uniform distribution of hash values will do. Source addresses are stored in a RAM table consisting of K "buckets" numbered 0 to k-1. All source addresses that map to the same integer value are stored in the same "bucket". While hashing increases speed, the implementation of hashing techniques in hardware is very difficult and costly.
It is therefore an object of the present invention to provide an improved apparatus and method for recognizing addresses.
It is a further object of the present invention to provide an apparatus and method for recognizing source addresses of information packets in rapid fashion for large numbers of addresses.
It is a further object of the present invention to provide an apparatus and method as recited in the preceding objectives and which can be inexpensively implemented with hardware.
It is yet a further object of the present invention to provide an apparatus and method as recited in the preceding objectives and which is implemented in a bridge for connecting LANs.